package com.ctrip.study.algorithm.leetcode;

public class HasCycle {
	
	static class ListNode {
		int val;
		ListNode next;

		ListNode(int x) {
			val = x;
			this.next = null;
		}

		public void setNext(ListNode next) {
			this.next = next;
		}
		
	}
	
	public boolean hasCycle(ListNode head) {
		if(head == null){
			return false;
		}
		ListNode firstKey = head;
		ListNode secondKey = head;
		while(firstKey.next != null && secondKey.next != null && secondKey.next.next != null){
			secondKey = secondKey.next.next;
			firstKey = firstKey.next;
			if(firstKey == secondKey){
				return true;
			}
		}
        return false;
    }
	
	
	public static void main(String[] args) {
		ListNode node1 = new ListNode(1);
		ListNode node2 = new ListNode(2);
		ListNode node3 = new ListNode(3);
		ListNode node4 = new ListNode(4);
		ListNode node5 = new ListNode(5);
		ListNode node6 = new ListNode(6);
		ListNode node7 = new ListNode(7);
		ListNode node8 = new ListNode(8);
		node1.next = node2;
		node2.next = node3;
		node3.next = node4;
		node4.next = node5;
		node5.next = node6;
		node6.next = node7;
		node7.next = node8;
		node8.next = null;
		System.out.println(new HasCycle().hasCycle(node1));
	}

}
